import java.util.ArrayList;
import java.util.List;
// https://leetcode.cn/problems/palindrome-partitioning/
public class Partition {
    class Solution {
        List<List<String>> res = new ArrayList<>();
        public List<List<String>> partition(String s) {
            backTracking(new ArrayList<>(),s,0);
            return res;
        }

        private void backTracking(List<String> path , String str , int startIndex)
        {

            if(startIndex == str.length())
            {
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i = startIndex ; i < str.length() ; i ++)
            {
                if(isPalindrome(str,startIndex,i)){
                    path.add(str.substring(startIndex,i+1));
                    backTracking(path,str,i + 1);
                }else{
                    continue;
                }
                path.remove(path.size()-1);
            }
        }

        private boolean isPalindrome(String str , int left , int right)
        {
            for(int i = left, j = right  ; i < j ; i ++ , j --)
            {
                if(str.charAt(i) != str.charAt(j))
                {
                    return false;
                }
            }
            return true;
        }
    }
}
